package com.wmx.datastructuresandalgorithms.sortalgorithm;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**********************************
 * @author wmx
 * @date 2019/8/30 9:58
 * @description:
 * @version 1.0
 * 算法 ---->先简单————复杂
 * 就可以将复杂的算法拆分简单问题 ---》逐步解决
 *
 *
 *  选择排序：假定第一个数就是最小的，记录第一个数的下标（minIndex）和值（min）。循环遍历所有的数min（最小值比较），
 *  如果最小值大于比较的数，替换最小值和下标 。经过一次循环后就得到数组中最小值得值和下标。然后交换位置.
 *  然后交换两个值的位置和下标。
 *
 *  优化：如果最小值的下标没有变化，说明假定的最小值就是最小值。不用交换
 *
 *
 *  为什么选择排序要不冒泡排序快呢?
 *   冒泡排序是在每次循环过程中进行交换可能会交换一次或者很多次，而选择排序，在一次循环后，进行交换。
 *   一次循环值交换一次，所以选择排序要比冒泡排序快。
 *
 ************************************/
public class SelectionSort {

    public static void main(String[] args) {
        //创建一个数组
      /*  int [] arr = {9,7,4,6,5};

        System.out.println("排序前："+ Arrays.toString(arr));
        selectionSort1(arr);
        System.out.println("排序后："+Arrays.toString(arr));
*/


        //创建100000条数据测试冒泡排序的时间
        int [] arr2 =new int[80000];
        for (int i = 0; i <80000 ; i++) {
            arr2[i] = (int)(Math.random()*800000);
        }
        //开始排序时间
        Date date = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:hh:ss");
        System.out.println("排序时的时间："+simpleDateFormat.format(date));

        selectionSort1(arr2);

        Date date1 = new Date();
        System.out.println("排序时的时间："+simpleDateFormat.format(date1));
        System.out.println(Arrays.toString(arr2));

    }




    public static void  selectionSort(int [] arr){
        for (int i = 0; i <arr.length-1 ; i++) {
            //假定i=0的时候就是最小值。
            int minIndex = i;
            int min = arr[minIndex];

            for (int j =i+1; j <arr.length; j++) {
                // 循环一次记录最小值位置
                if(min>arr[j]){
                    min = arr[j];
                    minIndex = j;
                }
            }
            // 如果minIndex  == i 说明假定的就是最小值
            if(minIndex != i){
                //交换位置
                arr[minIndex] =arr[i];
                arr[i] =min;
            }
           // System.out.println(Arrays.toString(arr));

        }
    };

    public static void selectionSort1(int [] arr){
        for (int i = 0; i <arr.length-1 ; i++) {
            int minIndex = i;
            int min = arr[minIndex];
            for (int j = i+1; j < arr.length; j++) {
                if(min>arr[j]){
                    min = arr[j];
                    minIndex = j ;
                }
            }

            if(minIndex!=i){
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
        }


    };
}
